package goleetcode

func waysToReachStairs(k int) int {
	type args struct {
		i, j int
		preDown bool
	}

	memo := map[args]int{}
	var dfs func(i, j int, preDown bool) int
	dfs = func(i, j int, preDown bool) int {
		if i > k + 1 {
			return 0
		}
		p := args{i, j, preDown}
		if v, ok := memo[p]; ok {
			return v
		}
		res := dfs(i + 1 << j, j + 1, false)
		if !preDown && i > 0 {
			res += dfs(i - 1, j, true)
		}
		if i == k {
			res++
		}
		memo[p] = res
		return res
	}
	return dfs(1, 0, false)
}